package day_2022_9_to_12.Day;

/**
 * @author haomin
 * @date 2022/09/12 23:26
 **/
public class Day10_5_Num312_MaxCoins {
    public int maxCoins(int[] nums) {
        int[] arr = new int[nums.length + 2];
        arr[0] = 1;
        arr[arr.length - 1] = 1;
        for(int i = 1; i < arr.length - 1; i++){
            arr[i] = nums[i - 1];
        }
        int[][] map = new int[arr.length][arr.length];
        for(int i = 1; i < map.length - 1; i++){
            map[i][i] = arr[i - 1] * arr[i] * arr[i + 1];
        }
        for(int start = map.length - 2; start > 0; start--){
            for(int end = start + 1; end < map.length - 1; end ++){
                int ans = 0;
                int p ;
                for(int i = start; i <= end; i++){
                    p = arr[start - 1] * arr[i] * arr[end + 1] + map[start][i - 1] + map[i + 1][ end];
                    //最后打爆i位置，则打爆i位置加上start到i - 1位置的得分 加上i + 1到end的得分就是得分
                    ans = Math.max(ans, p);
                }
                map[start][end] = ans;
            }
        }
        return map[1][map.length -2];
    }
}